package string.match;

/**
 * @Classname : FindTheIndexOfTheFirstOccurrenceInAString
 * @Description : 28. 找出字符串中第一个匹配项的下标
 * https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
 * @Author : chentianyu
 * @Date 2022/12/12 23:03
 */


public class FindTheIndexOfTheFirstOccurrenceInAString {
    /**
     * 方法一：穷举法
     * 时间复杂度：O(N^2)
     *
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr1(String haystack, String needle) {
        int m = haystack.length(), n = needle.length();
        for (int i = 0; i <= m - n; i++) {
            for (int j = 0; j < n; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) break;
                if (j == n - 1) return i;
            }
        }
        return -1;
    }

    /**
     * 方法二：KMP算法
     * 时间复杂度：O(m + n)
     * O(n)获取next数组，O(m)进行匹配
     *
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        int m = haystack.length(), n = needle.length(), j = 0;
        int[] next = getNext(needle);
        for (int i = 0; i < m; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == n) {
                return i - j + 1;
            }
        }
        return -1;
    }

    private int[] getNext(String s) {
        int m = s.length(), j = 0;
        int[] next = new int[m];
        // 遍历获取子串 s.substring(0, i) 的最长公共前后缀位置的下一位位置数组 next
        // 如字符串 aabaa 对应 next[4]，最长公共前后缀为 aa，下一位是b，其位置是3，所以 next[4] = 3
        // 前缀和后缀：如字符串 abc...xyz，前缀必须从 a 开始 且 不包含 z，后缀必须以 z 结尾 且 不包含 a
        for (int i = 1; i < m; i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
